package vj.linkedlist.sort;

import vj.linkedlist.Node;

public class MergeSort {
	
	
	public static Node mergeSort(Node head) {
		if(head == null || head.next == null)
			return head;
		Node mid = splitAtMiddle(head);
		Node a = mergeSort(head);
		Node b = mergeSort(mid);
		return sortedMerge(a, b);
		
	}
	
	public static Node splitAtMiddle(Node src) {
		if(src == null || src.next == null)
			return null;
		Node slow = src;
		Node fast = src.next;
		while(fast != null) {
			fast = fast.next;
			if(fast != null) {
				fast = fast.next;
				slow = slow.next;
			}
		}
		Node ret = slow.next;
		slow.next = null; // very important. End the fist list
		return ret;
		
	}
	
	public static Node sortedMerge(Node a, Node b) {
		Node last = null; // reference to the last node in the sorted list
		if(a == null)
			return b;
		if(b == null)
			return a;
		Node res = null;
		if (a.data < b.data) {
			res = a;
			last = a;
			a = a.next;
		}
		else {
			res = b;
			last = b;
			b = b.next;
		}
		while(true) {
			if(a == null) {
				last.next = b;
				break;
			}
			else if(b == null) {
				last.next = a;
				break;
			}
			if (a.data < b.data) {
				last.next = a;
				a = a.next;
			} else {
				last.next = b;
				b = b.next;
			}
			last = last.next;
		}
		return res;
	}
}
